
/*
回溯
连接：https://leetcode.cn/problems/n-queens/description/
题目：51. N 皇后

⾸先，我们在第⼀⾏放置第⼀个皇后，然后遍历棋盘的第⼆⾏，在可⾏的位置放置第⼆个皇后，然后
再遍历第三⾏，在可⾏的位置放置第三个皇后，以此类推，直到放置了 n 个皇后为⽌。
我们需要⽤⼀个数组来记录每⼀⾏放置的皇后的列数。在每⼀⾏中，我们尝试放置⼀个皇后，并检查
是否会和前⾯已经放置的皇后冲突。如果没有冲突，我们就继续递归地放置下⼀⾏的皇后，直到所有
的皇后都放置完毕，然后把这个⽅案记录下来。
在检查皇后是否冲突时，我们可以⽤⼀个数组来记录每⼀列是否已经放置了皇后，并检查当前要放置
的皇后是否会和已经放置的皇后冲突。对于对⻆线，我们可以⽤两个数组来记录从左上⻆到右下⻆的
每⼀条对⻆线上是否已经放置了皇后，以及从右上⻆到左下⻆的每⼀条对⻆线上是否已经放置了皇
后。
• 对于对⻆线是否冲突的判断可以通过以下流程解决：
1. 从左上到右下：相同对⻆线的⾏列之差相同；
2. 从右上到左下：相同对⻆线的⾏列之和相同。
因此，我们需要创建⽤于存储解决⽅案的⼆维字符串数组 solutions ，⽤于存储每个皇后的位置的
⼀维整数数组 queens ，以及⽤于记录每⼀列和对⻆线上是否已经有皇后的布尔型数组
columns 、 diagonals1 和 diagonals2 。
递归函数设计：void dfs(vector<vector<string>> &solutions, vector<int> &queens, int &n, int
row, vector<bool> &columns, vector<bool> &diagonals1, vector<bool> &diagonals2)
参数：row（当前需要处理的⾏数）；
返回值：⽆；
函数作⽤：在当前⾏放⼊⼀个不发⽣冲突的皇后，查找所有可⾏的⽅案使得放置 n 个皇后后不发⽣冲
突。
递归函数流程如下：
1. 结束条件：如果 row 等于 n ，则表⽰已经找到⼀组解决⽅案，此时将每个皇后的位置存储到字
符串数组 board 中，并将 board 存储到 solutions 数组中，然后返回；
2. 枚举当前⾏的每⼀列，判断该列、两个对⻆线上是否已经有皇后：
a. 如果有皇后，则继续枚举下⼀列；
b. 否则，在该位置放置皇后，并将 columns 、 diagonals1 和 diagonals2 对应的位置
设为 true ，表⽰该列和对⻆线上已经有皇后：
i. 递归调⽤ dfs 函数，搜索下⼀⾏的皇后位置。如果该⽅案递归结束，则在回溯时需要将
columns 、 diagonals1 和 diagonals2 对应的位置设为 false ，然后继续枚举
下⼀列；
*/
class Solution {
public: 
    bool checkcol[10]={false};//记录列
    bool checkdig1[20]={false};//记录主对角线
    bool checkdig2[20]={false};//记录副对角线
    vector<vector<string>> ret;
    vector<string> path;
    int size=0;
    vector<vector<string>> solveNQueens(int n) {
        size = n;
        path.resize(n);
        for(int i=0;i<n;i++)
        {
            path[i].append(n,'.');
        }
        dfs(0);
        return ret;
    }
    void dfs(int row)
    {
        if(row==size)
        {
            ret.push_back(path);
            return ;
        }

        for(int col = 0;col<size;col++)
        {
            if(!checkcol[col] && !checkdig1[row-col+size] && !checkdig2[row+col])
            {
                path[row][col] = 'Q';
                checkcol[col] = checkdig1[row-col+size] = checkdig2[col+row] = true;
                dfs(row+1);
                //恢复
                path[row][col] = '.';
                checkcol[col] = checkdig1[row-col+size] = checkdig2[col+row] = false;
            }
        }
    }
};